package MyMath;

import java.lang.reflect.Array;
import java.util.Arrays;

/**
 * 标准的“下一个排列”算法可以描述为：
 *
 *     从后向前查找第一个相邻升序的元素对 (i,j)，满足 A[i] < A[j]。此时 [j,end) 必然是降序
 *     在 [j,end) 从后向前查找第一个满足 A[i] < A[k] 的 k。A[i]、A[k] 分别就是上文所说的「小数」、「大数」
 *     将 A[i] 与 A[k] 交换
 *     可以断定这时 [j,end) 必然是降序，逆置 [j,end)，使其升序
 *     如果在步骤 1 找不到符合的相邻元素对，说明当前 [begin,end) 为一个降序顺序，则直接跳到步骤 4
 *
 * 该方法支持数据重复，且在 C++ STL 中被采用。
 */
public class Leetcode0031 {
    public static void nextPermutation(int[] nums) {
        if(nums == null || nums.length <= 1) {
            return ;
        }
        int len = nums.length;
        int i_index = len - 2;
        // 获取从右往左第一个逆序的，必须要大于
        while (i_index >=0 && nums[i_index] >= nums[i_index + 1]){
            i_index --;
        }
        // 获取从右往左第一个大于i_index的位置，必须要大于
        if(i_index >=0){
            int j_index = len -1;
            while (nums[j_index] <= nums[i_index]){
                j_index --;
            }
            swap(nums, i_index, j_index);
        }
        reverse(nums, i_index+1);
    }

    public static void swap(int[] nums,int i,int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

    // 交换i_index-1及其之后的
    public static void reverse(int[] nums, int start) {
        int left = start, right = nums.length - 1;
        while (left < right){
            swap(nums, left, right);
            left ++;
            right --;
        }
    }

    public static void main(String[] args) {
        int[] nums = new int[]{4,5,6,3,1,2,7};
        for(int i=0; i<10; i++){
            nextPermutation(nums);

            int[] newNums = new int[nums.length];
            System.arraycopy(nums,0, newNums, 0, nums.length);
            System.out.println(Arrays.toString(newNums));
        }
    }

}
